#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<int> lexicalOrder(int n)
    {
        std::vector<int> ans;
        ans.push_back(1);

        for (int i = 1; i < n; ++i)
        {
            int number = ans.back();
            if (number * 10 <= n)
            {
                number *= 10;
            }
            else
            {
                while (number >= n || number % 10 == 9)
                {
                    number /= 10;
                }
                ++number;
            }

            ans.push_back(number);
        }

        return ans;
    }
};